/*
 * @lc app=leetcode.cn id=25 lang=swift
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
        if head == nil { return head }
        /// 反转[a,b)之间的节点
        func reverse(_ a: ListNode?, _ b: ListNode?) -> ListNode? {
            var pre: ListNode? = nil
            var next: ListNode? = nil
            var cur: ListNode? = a
            while cur !== b {
                next = cur?.next
                cur?.next = pre
                pre = cur
                cur = next
            }
            /// 反转后的头结点
            return pre
        }

        var a: ListNode? = head
        var b: ListNode? = head
        for i in 0..<k {
            // 不足 k 个，不需要反转，base case
            if b == nil { return head }
            b = b?.next
        }

        // 反转前k个
        let newHead = reverse(a, b)
        a?.next = reverseKGroup(b, k)
        return newHead
    }
}
// @lc code=end

